208. 实现 Trie (前缀树)

为保证权益，题目请参考 208. 实现 Trie (前缀树)(From LeetCode).

解决方案1

CPP

#include <iostream>
#include <string>
#include <map>
using namespace std;

// -------------------------------------------------------------------------- //

class Node
{
    char val;
    map<char, Node *> nextMap;

public:
    Node(char val_)
    {
        this->val = val_;
    }

    // 获取对应节点
    Node *getOrCreateNextNode(char val)
    {
        if (nextMap.find(val) != nextMap.end())
        {
            return nextMap.at(val);
        }
        else
        {
            Node *tmp = new Node(val);
            nextMap.insert(map<char, Node *>::value_type(val, tmp));
            return tmp;
        }
    }

    Node *getNextNode(char val)
    {
        if (nextMap.find(val) != nextMap.end())
        {
            return nextMap.at(val);
        }
        else
        {
            return nullptr;
        }
    }

    bool hasNextNodes()
    {
        return this->nextMap.size() != 0;
    }

    bool reachEnd()
    {
        return this->nextMap.find('$') != this->nextMap.end();
    }
};

class Trie
{
private:
    Node *head;

public:
    /** Initialize your data structure here. */
    Trie()
    {
        this->head = new Node('0');
    }

    /** Inserts a word into the trie. */
    void insert(string word)
    {
        Node *tmp = head;
        for (int i = 0; i < word.length(); i++)
        {
            tmp = tmp->getOrCreateNextNode(word[i]);
        }
        tmp->getOrCreateNextNode('$');
    }

    /** Returns if the word is in the trie. */
    bool search(string word)
    {
        Node *tmp = head;
        for (int i = 0; i < word.length(); i++)
        {
            tmp = tmp->getNextNode(word[i]);
            if (tmp == nullptr)
            {
                return false;
            }
        }

        return tmp->reachEnd();
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix)
    {
        Node *tmp = head;
        for (int i = 0; i < prefix.length(); i++)
        {
            tmp = tmp->getNextNode(prefix[i]);
            if (tmp == nullptr)
            {
                return false;
            }
        }
        return true;
    }
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */

// -------------------------------------------------------------------------- //

int main()
{
    Trie *t = new Trie();
    t->insert("app");
    cout << t->search("app") << endl;
    return 0;
}

Python

# 208. 实现 Trie (前缀树)
# https://leetcode-cn.com/problems/implement-trie-prefix-tree/

################################################################################

class Trie:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.wordTree = {}


    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """

        t = self.wordTree
        for s in word:
            if s not in t:
                t[s] = {}
            t = t[s]
        t["end"] = True


    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        t = self.wordTree
        for s in word:
            if s not in t:
                return False
            else:
                t = t[s]

        return "end" in t

    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        t = self.wordTree
        for s in prefix:
            if s not in t:
                return False
            else:
                t = t[s]

        return True


# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)



################################################################################


if __name__ == "__main__":
    pass

解决方案2

CPP

class Trie {
public:

	struct TreeNode {
		char ch;
		bool end;
		TreeNode * son[26];
		TreeNode(char ch_ = '-') {
			ch = ch_;
			end = false;
			for (int i = 0; i < 26; ++i) {
				son[i] = NULL;
			}
		}
	};
	
	TreeNode* root;


	/** Initialize your data structure here. */
	Trie() {
		root = new TreeNode();
	}

	/** Inserts a word into the trie. */
	void insert(string word) {
		TreeNode* p = root;
		for (unsigned i = 0; i < word.length(); ++i) {
			if (p->son[word[i] - 'a'] == NULL) {
				TreeNode* q = new TreeNode(word[i]);
				p->son[word[i] - 'a'] = q;
				p = q;
			}
			else {
				p = p->son[word[i] - 'a'];
			}
		}
		p->end = true;
	}

	/** Returns if the word is in the trie. */
	bool search(string word) {
		TreeNode* p = root;
		for (unsigned i = 0; i < word.length(); ++i) {
			if (p->son[word[i] - 'a'] == NULL) {
				return false;
			}
			else {
				p = p->son[word[i] - 'a'];
			}
		}
		if (p->end == true)
			return true;
		else
			return false;
	}

	/** Returns if there is any word in the trie that starts with the given prefix. */
	bool startsWith(string prefix) {
		TreeNode* p = root;
		for (unsigned i = 0; i < prefix.length(); ++i) {
			if (p->son[prefix[i] - 'a'] == NULL) {
				return false;
			}
			else {
				p = p->son[prefix[i] - 'a'];
			}
		}
		return true;
	}
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */